// https://www.lintcode.com/problem/combination-sum/my-submissions

class Solution {
public:
    /**
     * @param candidates: A list of integers
     * @param target: An integer
     * @return: A list of lists of integers
     */
    
    void helper (vector<int> candidates, int target, vector<vector<int>>& result, int start, vector<int>& tmp)
    {
        if (target == 0) 
        {
            result.push_back(tmp);
            return;
        }
        for (int i = start; i < candidates.size(); ++i)
        {
            if (candidates[i] > target) return; // 剪枝
            if (i != start && candidates[i] == candidates[i - 1]) continue; //去重
            tmp.push_back(candidates[i]);
            helper(candidates, target - candidates[i], result, i, tmp);
            // 每个数字可以重复用，所以startIndex传入下一层递归时不加1
            tmp.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        vector<vector<int>> result;
        vector<int> tmp;
        sort(candidates.begin(), candidates.end());
        helper(candidates, target, result, 0, tmp);
        return result;
    }
};


class Solution {
public:
    void helper(vector<int>& candidates, vector<int>& tmp, int start, int sum, int target, vector<vector<int>>&res) {
        if (sum >= target) {
            if (sum == target) {
                res.push_back(tmp);
            }
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            if (candidates[i] > target) continue; // 剪枝，上面是排序了所以return。这边注意是continue
            tmp.push_back(candidates[i]);
            sum += candidates[i];
            helper(candidates, tmp, i, sum, target, res); // 注意从i开始
            tmp.pop_back();
            sum -= candidates[i]; // 注意
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> tmp;
        helper(candidates, tmp, 0, 0, target, res);
        return res;
    }
};